﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1.DataStructure
{
    public class Sort
    {
        static void Main()
        {
            DateTime sTime = DateTime.Now;
            //int[] array = {1,3,2,0,7,8,9,5};
            //int[] array = { 0,1,3,2,4,5,6};
            int[] array = { 3,2,1 };
            //int[] array = { 5,4,3,2,1 };
            //int[] array = { 1,3,2,4,5};
            Console.WriteLine("排序前：");
            foreach (int i in array)
            {
                Console.Write(i+" ");
            }
            //int count = BubbleSort(array);
            QSort(ref array, 0, array.Length-1);
            Console.WriteLine("排序后：");
            foreach (int i in array)
            {
                Console.Write(i + " ");
            }
            //Console.WriteLine(" 循环次数"+count);
            DateTime eTime = DateTime.Now;
            Console.WriteLine("消耗时间:{0}",eTime-sTime);
            Console.Read();
        }

        #region 冒泡排序
        static int BubbleSort(int[] intArray)
        {
            int count = 0;
            int temp;
            bool flag = true;
            for (int i = 0; i < intArray.Length && flag; i++)
            {
                flag = false;
                //for (int j = 0; j < intArray.Length - 1; j++)
                //{
                //    if (intArray[j] > intArray[j + 1])
                //    {
                //        temp = intArray[j];
                //        intArray[j] = intArray[j + 1];
                //        intArray[j + 1] = temp;
                //        flag = true;
                //    }
                //    count++;
                //}

                for (int j = intArray.Length - 2; j >= i; j--)
                {
                    if (intArray[j] > intArray[j + 1])
                    {
                        temp = intArray[j];
                        intArray[j] = intArray[j + 1];
                        intArray[j + 1] = temp;
                        flag = true;
                    }
                    count++;
                }
            }
            return count;
        }
        #endregion

        #region 简单快速排序
        
        private static void QSort(ref int[] array, int low, int hei)
        {
            int pivot;
            if (low < hei)
            {
                pivot = Partition(ref array, low, hei);
                QSort(ref array, low, pivot - 1);
                QSort(ref array, pivot + 1, hei);
            }
        }
        
        private static int Partition(ref int[] array, int low, int hei)
        {
            int pivotKey = array[low];
            while (low < hei)
            {//从数组的两端向中间扫描
                while (low < hei && array[hei] >= pivotKey)
                { hei--; }
                Swap(array, low, hei);//将比中枢轴小的记录交换到低端
                while(low<hei && array[low]<=pivotKey)
                {low++;}
                Swap(array,low,hei);//将比枢轴大的记录交换到高端
            }
            return low;
        }
        #endregion

        //交换
        private static int[] Swap(int[] array,int i,int j)
        {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            return array;
        }

    }
}
